package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by Ghost on 2014/11/11.
 */
public class Count_and_Say {
    public String countAndSay(int n) {
        Queue<Integer> queue = new LinkedList<Integer>();
        Queue<Integer> queue1= new LinkedList<Integer>();
        if(n==1)
            return "1";
        queue.offer(1);
        for(int i=2;i<=n;i++){
            while(!queue.isEmpty()){
                int num = 1;
                int a = queue.poll();
                while(!queue.isEmpty()){
                    int b = queue.peek();
                    if(b==a){
                        queue.poll();
                        num++;
                    }
                    else{
                        break;
                    }
                }
                queue1.offer(num);
                queue1.offer(a);
            }
            Queue c = queue1;
            queue1 = queue;
            queue = c;
        }
        StringBuilder stringBuilder = new StringBuilder();
        while(!queue.isEmpty()){
            int a = queue.poll();
            stringBuilder.append(a);
        }
        return stringBuilder.toString();
    }
    public static void main(String[] args){
        Count_and_Say count_and_say = new Count_and_Say();
        System.out.println(count_and_say.countAndSay(5));
    }
}
